package ua.yandex.prioritymap;

import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class Heap<Key> implements Iterable<Key> {
    private Key[] heap;                   
    private int size;                       
    private Comparator<Key> comparator;  

    public Heap(int initCapacity) {
        heap = (Key[]) new Object[initCapacity + 1];
        size = 0;
    }

    public Heap() {
        this(1);
    }

    public Heap(int initCapacity, Comparator<Key> comparator) {
        this.comparator = comparator;
        heap = (Key[]) new Object[initCapacity + 1];
        size = 0;
    }

    public Heap(Comparator<Key> comparator) {
        this(1, comparator);
    }

    public Heap(Key[] keys) {
        size = keys.length;
        heap = (Key[]) new Object[keys.length + 1]; 
        for (int i = 0; i < size; i++)
            heap[i+1] = keys[i];
        for (int k = size/2; k >= 1; k--)
            sink(k);
        
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public Key max() {
        if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
        return heap[1];
    }

    private void resize(int capacity) {
        assert capacity > size;
        Key[] temp = (Key[]) new Object[capacity];
        for (int i = 1; i <= size; i++) temp[i] = heap[i];
        heap = temp;
    }

    public void insert(Key x) {

        // double size of array if necessary
        if (size >= heap.length - 1) resize(2 * heap.length);

        // add x, and percolate it up to maintain heap invariant
        heap[++size] = x;
        swim(size);
    }

    public Key delMax() {
        if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
        Key max = heap[1];
        swap(1, size--);
        sink(1);
        heap[size+1] = null;     // to avoid loiterig and help with garbage collection
        if ((size > 0) && (size == (heap.length - 1) / 4)) resize(heap.length / 2);
        return max;
    }

    private void swim(int k) {
        while (k > 1 && less(k/2, k)) {
            swap(k, k/2);
            k = k/2;
        }
    }

    private void sink(int k) {
        while (2*k <= size) {
            int j = 2*k;
            if (j < size && less(j, j+1)) j++;
            if (!less(k, j)) break;
            swap(k, j);
            k = j;
        }
    }

    private boolean less(int i, int j) {
        if (comparator == null) {
            return ((Comparable<Key>) heap[i]).compareTo(heap[j]) < 0;
        }
        else {
            return comparator.compare(heap[i], heap[j]) < 0;
        }
    }

    private void swap(int i, int j) {
        Key temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    private boolean isMaxHeap() {
        return isMaxHeap(1);
    }

    private boolean isMaxHeap(int k) {
        if (k > size) return true;
        int left = 2*k, right = 2*k + 1;
        if (left  <= size && less(k, left))  return false;
        if (right <= size && less(k, right)) return false;
        return isMaxHeap(left) && isMaxHeap(right);
    }



    @Override
    public Iterator<Key> iterator() { return new HeapIterator(); }

    private class HeapIterator implements Iterator<Key> {

        // create a new pq
        final    private Heap<Key> copy;

        // add all items to copy of heap
        // takes linear time since already in heap order so no keys move
        public HeapIterator() {
            if (comparator == null) copy = new Heap<>(size());
            else                    copy = new Heap<>(size(), comparator);
            for (int i = 1; i <= size; i++)
                copy.insert(heap[i]);
        }

        @Override
        public boolean hasNext()  { return !copy.isEmpty();                     }
        
        @Override
        public void remove()      { throw new UnsupportedOperationException();  }

        @Override
        public Key next() {
            if (!hasNext()) throw new NoSuchElementException();
            return copy.delMax();
        }
    }


}
